Negeri Victoria pada asalnya adalah rumah kepada banyak bangsa pribumi yang telah menduduki tanah itu untuk beribu-ribu tahun.[1] Menurut Gary Presland, Orang Asli telah tinggal di Victoria selama kira-kira 40,000 tahun,[2] hidup dalam keadaan separa nomad memancing, memburu dan mengumpul, dan penternakan belut.[3]

Di Tapak Arkeologi Keilor perdiangan manusia digali pada tahun 1971 telah ditarikh radiokarbon kepada kira-kira 31,000 tahun BP, menjadikan Keilor salah satu daripada lokasi terawal kediaman manusia di Australia.[4] Tengkorak ditemui di tapak itu telah bertarikh di antara 12,000[5] dan 14,700 tahun BP.[4]

Tapak arkeologi di Tasmania dan di Selat Bass Kepulauan telah bertarikh antara 20,000 – 35,000 tahun yang lalu, apabila paras laut 130 meter di bawah paras sekarang membolehkan Orang Asli untuk bergerak merentasi kawasan selatan Victoria dan seterusnya ke laluan darat dataran Bassian ke Tasmania sekurang-kurangnya 35,000 tahun yang lalu.[6][7]

Ketika Zaman Ais kira-kira 20,000 tahun BP, kawasan yang kini teluk Port Phillip dahulunya tanah kering, dan sungai Yarra dan Werribee bergabung mengalir melalui tanjung kemudian ke selatan dan barat daya melalui dataran Bassian sebelum bertemu laut di sebelah barat. Tasmania dan pulau-pulau Selat Bass terpisah dari tanah besar Australia sekitar 12,000 BP, apabila paras laut adalah kira-kira 50m di bawah paras ketika.[8] Port Phillip telah dibanjiri oleh kenaikan paras laut pasca glasier antara 8000 dan 6000 tahun yang lalu.[9]

Sejarah lisan dan cerita-cerita penciptaan dari bahasa Wada wurrung, Woiwurrung dan Bun wurrung menggambarkan banjir teluk berkenaan. Hobsons Bay pernah menjadi tanah memburu kanggaru. Kisah penciptaan menerangkan bagaimana Bunjil bertanggungjawab kepada pembentukan teluk,[7] atau teluk itu dibanjiri ketika sungai Yarra telah dicipta (Yarra Creation Story.[10])